package com.husk.leetcode.basic;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * <p>
 * 剑指 Offer 41. 数据流中的中位数
 * https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/
 * </p>
 *
 * @author hushunke@foxmail.com
 * @since 2021/7/16
 */
public class MedianFinder {

    Queue<Integer> queueA;
    Queue<Integer> queueB;

    /**
     * 构建大顶堆和小顶堆
     *
     * initialize your data structure here.
     */
    public MedianFinder() {
        queueA = new PriorityQueue<>();// 小顶堆，保存较大的一半
        queueB = new PriorityQueue<>(Comparator.reverseOrder());//大顶堆，保存较小的一半
    }

    public void addNum(int num) {
        if (queueA.size() != queueB.size()) {
            queueA.add(num);
            queueB.add(queueA.poll());
        } else {
            queueB.add(num);
            queueA.add(queueB.poll());
        }
    }

    public double findMedian() {
        return queueA.size() == queueB.size() ? (queueA.peek() + queueB.peek()) / 2.0 : queueA.peek();
    }

}
